﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0004_MoveZeros
    {
        // 移动零

        // 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

        // 说明：
        // 1.必须在原数组上操作，不能拷贝额外的数组。
        // 2.尽量减少操作次数。

        public void Test()
        {
            var nums = new int[] { 1, 0, 0, 3, 1, 0, 2, 2 };
            MoveZeros(nums);

            foreach (var item in nums)
            {
                Console.Write(item);
            }
            Console.Read();
        }

        // 找到零并记录其位置，继续循环若不为零则替换至记录位，记录位向后一位重复
        // 时间：O(n)
        // 空间：O(1)
        public void MoveZeros(int[] nums)
        {
            int lPointer = -1;
            for (int i = 0; i < nums.Length; i++)
            {
                if (lPointer < 0 && nums[i] == 0)
                {
                    lPointer = i;
                }
                if (lPointer >= 0 && nums[i] != 0)
                {
                    nums[lPointer] = nums[i];
                    nums[i] = 0;
                    lPointer++;
                }
            }
        }

        public void MoveZeroes1(int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)
                if (nums[i] == 0)
                    for (int j = i + 1; j < nums.Length; j++)
                        if (nums[j] != 0)
                        {
                            nums[i] = nums[j];
                            nums[j] = 0;
                            break;
                        }
        }
    }
}
